package LeetCode;

import java.util.ArrayList;
import java.util.List;

public class LC_417_PacificAtlanticWaterFlow {

    public static void main(String[] args) {

    }

    public class Solution {
        int dx[] = {0, 0, -1, 1};
        int dy[] = {1, -1, 0, 0};

        private void flow(boolean visited[][], int matrix[][], int x, int y, int n, int m) {
            visited[x][y] = true;
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (!visited[nx][ny] && matrix[nx][ny] >= matrix[x][y])
                        flow(visited, matrix, nx, ny, n, m);
                }
            }
        }

        public List<int[]> pacificAtlantic(int[][] matrix) {
            List<int[]> res = new ArrayList<>();
            int n = matrix.length;
            if (n == 0) return res;
            int m = matrix[0].length;
            boolean PV[][] = new boolean[n][m];
            boolean AV[][] = new boolean[n][m];
            for (int i = 0; i < n; i++) {
                flow(PV, matrix, i, 0, n, m);
                flow(AV, matrix, i, m - 1, n, m);
            }
            for (int i = 0; i < m; i++) {
                flow(PV, matrix, 0, i, n, m);
                flow(AV, matrix, n - 1, i, n, m);
            }
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    if (PV[i][j] && AV[i][j])
                        res.add(new int[]{i, j});
            return res;
        }

    }
}